import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class ListNode{
    public ListNode next;
    public int val;
    public ListNode(int val){
        this.val = val;
    }
}
public class TextDemo {
    public static ListNode mergeTwoListsDepth(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }else if(list1.val>list2.val){
            list2.next = mergeTwoListsDepth(list1,list2.next);
            return list2;
        }else{
            list1.next = mergeTwoListsDepth(list1.next,list2);
            return list1;
        }
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prevhead = new ListNode(-1);
        ListNode cur = prevhead;
        while(list1!=null&&list2!=null){
            if(list1.val>list2.val){
                cur.next = list2;
                list2 = list2.next;
            }else{
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if(list1==null){
            cur.next = list2;
        }else{
            cur.next = list1;
        }
        return prevhead.next;

    }
    public static ListNode partition(ListNode head, int x) {
        if(head==null){
            return null;
        }
        ListNode smallHeap = new ListNode(0);
        ListNode small = smallHeap;
        ListNode largeHeap = new ListNode(-1);
        ListNode large = largeHeap;
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = head;

            }else{
                large.next = head;
                large = head;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHeap.next;
        return smallHeap.next;
    }
    public static boolean chkPalindrome(ListNode head) {
        // write code here
        // write code here
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){

            fast = fast.next.next;
            slow = slow.next;
        }
        //reverse
        ListNode prev = null;
        ListNode next = null;
        ListNode cur = slow;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        slow = head;
        fast = prev;
        while(slow!=fast){
            if(slow.val!=fast.val){
                return false;
            }
            if(slow.next!=fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next;

        }
        return true;
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode PA = headA;
        ListNode PB = headB;
        while(PA!=PB){
            PA = PA==null?headB:PA.next;
            PB = PB==null?headA:PB.next;
        }
        return PA;

    }
    public static boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;

    }
    public static boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        String[] str = s.split("");
        if(str.length%2!=0){
            return false;
        }
        for(int i = 0;i<str.length;i++){
            if(str[i].equals("(")||str[i].equals("[")||str[i].equals("{")){
                stack.push(str[i]);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    String tem = stack.pop();
                    String tmp = str[i];
                    if(!((tem.equals("(")&&tmp.equals(")"))||(tem.equals("[")&&tmp.equals("]"))||(tem.equals("{")&&tmp.equals("}")))){
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();

    }
    public static boolean isValidMap(String s) {
        if(s.length()%2 !=0){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for(int i = 0;i<s.length();i++){
            char t = s.charAt(i);
            if(map.containsKey(t)){
                if(stack.isEmpty()||map.get(t)!=stack.pop()){
                    return false;
                }
            }else{
                stack.push(t);
            }
        }
        return stack.isEmpty();

    }
    public static void main(String[] args) {
        boolean s = isValid("()[]{}");
        Map<Character,Character> map = new HashMap<>();
        System.out.println(s);



    }
}
